\section{Reverse Quantiles}
\label{app:binsearch}

\begin{algorithm}[tbp]
\caption{ReverseQuantile($Q$, $n$, $x$)} 
\label{alg:reverse-quantile}

{\bf Input:} Quantile $\epsilon$-sketch $Q$ of a stream of size $n$; a number $x$

{\bf Output:} $i$, an estimate of the index of $x$ in the stream

\begin{algorithmic}[1]
\STATE $lo = 0$, $hi = n$
\WHILE{$lo < hi$}
  \STATE $mid = (lo + hi)/2$
  \STATE $v = $ result of a $mid/n$ query to $Q$
  \IF{$v \leq r$}
    \STATE $lo = mid + 1$
  \ELSE
      \STATE $hi = mid$
  \ENDIF
\ENDWHILE
\STATE {\bf return} $lo$
\end{algorithmic}
\end{algorithm}

The algorithms in this paper assume that it is possible to use any quantile $\epsilon$-sketch to perform a reverse quantile query, i.e., for any value $x$, returning the number of items in the stream at most this large. We show how this is possible using a simple binary search algorithm in this section, illustrated in Algorithm~\ref{alg:reverse-quantile}.


Note that due to the comparison in line 5 of Algorithm~\ref{alg:reverse-quantile}, the value returned is that of the last query that returns a number less than or equal to $x$, call it $i$. If the true index of $x$ is $j$, then by the property of quantile sketches we know that $|i - j| \leq \epsilon n$. Hence, this algorithm has additive error at most $\epsilon n$.

\begin{comment}
Note that due to the comparison in line 6 of Algorithm~\ref{alg:reverse-quantile}, the value returned is the number of elements in the sketch that are at most $x$. That is, if the original values in the stream were (in increasing order) $X_1, \ldots, X_n$ and the quantile sketch stores the values (also increasing) $X_{i_1}, \ldots, X_{i_k}$, then the algorithm stops when it finds the index $j$ such that $X_{i_j} \leq x < X_{i_{j+1}}$. 

Let $i$ be the real position of the value $x$ in the stream, that is, $X_i \leq x < X_{i+1}$. Then, we have that 
$$X_{i_j} \leq X_i \leq x < X_{i+1} \leq X_{i_{j+1}}$$
since $i$ is the greatest index such that $X_i \leq x$, and also since $i+1$ is the smallest index such that $x < X_{i+1}$. Now, we know from Observation~\ref{obs:sketchvalues} that $i_{j+1} - i_j \leq 2\epsilon n$, so it follows from the above relationship that $i - i_j \leq 2\epsilon n$. As a result, we have that the result of Algorithm~\ref{alg:reverse-quantile} is a value $lo = i_j$ such that $i - 2\epsilon n \leq i_j \leq i$, i.e., it has one-sided additive error of at most $2\epsilon n$. 
\end{comment}

\balance
